package cn.springcloud.fix.demo.leecode;

public class MaxSubArray {

    public static void main(String[] args) {
        int[] arr1 = new int[]{-2, 1, -3, 9, -1, 8};
        int[] arr2 = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int res = maxSubArray3(arr1);
        System.out.println(res);
    }

    // 1.暴力破解法——时间效率O(N^3)
    public static int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int sum;
        for (int i = 0; i < nums.length; i++) {// 子序列左端点
            for (int j = i; j < nums.length; j++) {// 子序列右端点
                sum = 0;
                for (int k = i; k <= j; k++) {//暴力计算
                    sum += nums[k];
                }
                if (sum > max) {
                    max = sum;
                }
            }
        }
        return max;
    }

    // 2.改进暴力法——时间效率O(N^2)
    public int maxSubArray2(int[] nums) {
        int max = Integer.MIN_VALUE;
        int sum;
        for (int i = 0; i < nums.length; i++) {// 子序列左端点
            sum = 0;
            for (int j = i; j < nums.length; j++) {// 子序列右端点
                sum += nums[j];// 这里就相当于每次根据前一次的序列来计算新的序列
                if (sum > max)
                    max = sum;
            }
        }
        return max;
    }

    // -2, 1, -3, 9, -1, 8
    public static int maxSubArray3(int[] nums) {
        int pre = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (pre < 0) {
                pre = nums[i];//当前数小于0 肯定会舍去（否则将会影响接下来的和），换为下一个数
            } else {
                pre += nums[i];//如果当前数不小于0，那么他会对接下来的和有积极影响
            }
            if (pre > max) {
                max = pre;
            }
        }
        return max;
    }
}
